//
// Description: 5791. 统计子岛屿
// Created by Loading on 2021/6/20.
//

#include <bits/stdc++.h>

using namespace std;

//每个岛屿的陆地坐标集合
vector<vector<pair<int, int>>> detail_grid2;

//回溯访问
void visit(vector<vector<int>> &grid, int i, int j, vector<pair<int, int>> &vec) {
    //坐标加入集合
    vec.emplace_back(pair<int, int>{i, j});
    //访问过的置为2
    grid[i][j] = 2;
    //四个方向回溯
    //左
    if (j - 1 >= 0 && grid[i][j - 1] == 1) {
        visit(grid, i, j - 1, vec);
    }
    //右
    if (j + 1 < grid[i].size() && grid[i][j + 1] == 1) {
        visit(grid, i, j + 1, vec);
    }
    //上
    if (i - 1 >= 0 && grid[i - 1][j] == 1) {
        visit(grid, i - 1, j, vec);
    }
    //下
    if (i + 1 < grid.size() && grid[i + 1][j] == 1) {
        visit(grid, i + 1, j, vec);
    }
}

int countSubIslands(vector<vector<int>> &grid1, vector<vector<int>> &grid2) {
    for (int i = 0; i < grid2.size(); i++) {
        for (int j = 0; j < grid2[i].size(); j++) {
            if (grid2[i][j] == 1) {
                vector<pair<int, int>> vec;
                visit(grid2, i, j, vec);
                detail_grid2.emplace_back(vec);
            }
        }
    }

    int count = 0;
    for (auto &grid : detail_grid2) {
        bool flag = true;
        for (auto &p : grid) {
            if (grid1[p.first][p.second] != 1) {//存在某个岛屿的某个格子未在 grid1 中出现
                flag = false;
                break;
            }
        }
        if (flag) {
            ++count;
        }
    }

    return count;
}

int main() {
    vector<vector<int>> grid1 = {{1, 0, 1, 0, 1},
                                 {1, 1, 1, 1, 1},
                                 {0, 0, 0, 0, 0},
                                 {1, 1, 1, 1, 1},
                                 {1, 0, 1, 0, 1}};
    vector<vector<int>> grid2 = {{0, 0, 0, 0, 0},
                                 {1, 1, 1, 1, 1},
                                 {0, 1, 0, 1, 0},
                                 {0, 1, 0, 1, 0},
                                 {1, 0, 0, 0, 1}};

    cout << countSubIslands(grid1, grid2) << endl;
}